#include "memorypool.h"

#define MIN_ALIGNMENT_SIZE 8

#define UT_MAX(a,b)   (a>b?a:b)
#define UT_CALC_ALIGN(n,m) (( n + ((m) - 1) ) & ~( (m) - 1 ))
#define UT_IS_POW2(n)  ( (n & (n-1)) == 0 )

// We need a MemoryArea object to monitor memory area status,
// this may take extra size.
#define MEM_AREA_EXTRA_SIZE UT_CALC_ALIGN(sizeof(MemoryArea), MIN_ALIGNMENT_SIZE)

// A memory area should at least be capacable to store two MemoryArea object
// In that it may be splitted into two parts
#define MEM_AREA_MIN_SIZE   (2 * MEM_AREA_EXTRA_SIZE)

/**
 * @brief log2
 * calculate ceil value of log2(n)
 * @param num
 * @return value>=1
 */
inline int ceilLog2(size_t num)
{
    num -= 1;
    int exp = 0;
    for( ;num!=0; num>>=1) {
        exp++;
    }

    return exp;
}

/**
 * @brief MEM_AREA_EXTRA_SIZE
 * Why it's using double size of MemoryArea as extra size of a pool?
 * An area can be divided into two areas at a lower level, with half the original size
 * respectively.
 */


MemoryPool::MemoryPool(size_t blockSize)
{
    BLOCK_SIZE = blockSize;
    addBlock( BLOCK_SIZE );

#ifndef NDBG
    requestSum = 0;
    allocSum = 0;
    recycleSize = 0;
    recycleAlloc = 0;
#endif

}

MemoryPool::~MemoryPool()
{
    destroy();
}

void MemoryPool::addBlock(size_t size)
{
    byte* newBlock = (byte*)malloc( size );
    if( !newBlock )
    {
        MemoryException me( "MemoryPool:No enough memory for new block" );
        throw me;
    }

    currentPosition = newBlock;
    remainSizeInCurBlock = size;
    blocks.push_back( newBlock );
}

void* MemoryPool::allocate(size_t size)
{
    size_t toAlloc = UT_CALC_ALIGN( (size+sizeof(MemoryArea)), MIN_ALIGNMENT_SIZE );

#ifndef NDBG
    requestSum += size;
    allocSum += toAlloc;
#endif

    ASSERT_MSG( toAlloc <= BLOCK_SIZE, "Can not allocate memory for size bigger than single block" );

    byte* ret = 0;
    MemoryArea* area = 0;

    if( remainSizeInCurBlock >= toAlloc ) // We happen to have enough size in blocks
    {
        ret = currentPosition + sizeof(MemoryArea);
        area = (MemoryArea*)currentPosition;
        area->setSize(toAlloc);
        //cout<<"Request="<<size<<" Alloc="<<toAlloc<<"Area Size="<<area->getSize()<< "sizeofMemArea:"<<sizeof(MemoryArea)<<endl;
        remainSizeInCurBlock -= toAlloc;
        currentPosition += toAlloc;
    }
    else
    {
        int index = ceilLog2(toAlloc);
        //cout<<"Alloc index="<<index<<endl;
        for( int i=index; i<RECYCLE_MAX_INDEX; i++ )
        {
            if( recycleList[i].empty() ) continue;
            area = recycleList[i].front();
            if( i != index )
            {
                area->setSize(toAlloc);
                size_t remainSize = area->getSize() - toAlloc;
                MemoryArea* area2 = (MemoryArea*)((byte*)area + toAlloc );
                area2->setSize(remainSize);
                area2->setFree(true);
                int index2 = ceilLog2( remainSize ) - 1;
                if( UT_IS_POW2(remainSize) )
                {
                    index2++;
                }
                recycleList[index2].push_front(area2);
            }

#ifndef NDBG
            recycleAlloc += area->getSize();
#endif
            recycleList[i].erase(recycleList[i].begin());
            ret = (byte*)area;
            break;
        }

        if( !ret ) //Cannot find available space from block/recycleList, expand block
        {
            addBlock(BLOCK_SIZE);
            ret = currentPosition + sizeof(MemoryArea);
            area = (MemoryArea*)currentPosition;
            area->setSize(toAlloc);

            remainSizeInCurBlock -= toAlloc;
            currentPosition += toAlloc;
        }
    }

    ASSERT( ret && area );

    area->magicNumber = MEM_AREA_MAGIC_N;
    area->setFree(false);
    //printf("area=%x, ret=%x, free=%d\n", (unsigned int)area, (unsigned int)ret, area->isFree());
    return (void*)ret;
}

void MemoryPool::recycle(void *ptr)
{
    //printf("Recycle=%x\n",(unsigned int)ptr );
    MemoryArea* area = (MemoryArea*)((byte*)ptr - sizeof(MemoryArea));

    // Check memory leak / illegal release
    ASSERT( area->isFree() == false );
    ASSERT( area->magicNumber == MEM_AREA_MAGIC_N );

    size_t size = area->getSize();

#ifndef NDBG
    recycleSize += size;
#endif
    int index = ceilLog2(size) - 1;
    if( UT_IS_POW2(size) )
    {
        index ++; // Put 2^n to a higher index
    }
    ASSERT(index < RECYCLE_MAX_INDEX);
    area->setFree(true);
    recycleList[index].push_front(area);
}

/**
 * @brief MemoryPool::destroy
 * Destroy all blocks allocated for this pool
 */
void MemoryPool::destroy()
{
    for( vector<byte*>::iterator i = blocks.begin();
         i != blocks.end();
         i++ )
    {
        free(*i);
    }

    blocks.clear();

    for( int i = 0; i< RECYCLE_MAX_INDEX; i++ )
    {
        if( recycleList[i].empty() ) continue;
        recycleList[i].clear();
    }

    currentBlock = 0;
    currentPosition = 0;
    remainSizeInCurBlock = 0;

#ifndef NDBG
    requestSum = 0;
    allocSum = 0;
    recycleSize = 0;
    recycleAlloc = 0;
#endif

}

void MemoryPool::report()
{
    cout<<"\n======MemoryPool report======"<<endl;
#ifndef NDBG
    cout<<"Requested = "<<requestSum<<" bytes. Allocated = "<<allocSum<<" bytes";
    double ratio = 0.0;
    if( allocSum )
    {
        ratio = 1.0*requestSum/allocSum;
    }
    cout<<" ratio="<<ratio<<endl;
    cout<<"Recycled = "<<recycleSize<<" bytes. Allocated From Recycle = "<< recycleAlloc<<" bytes";
    ratio = 0.0;
    if( recycleSize )
    {
        ratio = 1.0 * recycleAlloc / recycleSize;
    }
    cout<<" ratio="<<ratio<<endl;
#endif
    cout<<"#### Blocks"<<endl;
    for( size_t i=0; i<blocks.size(); i++ )
    {
        printf("#%d:\taddr:%x\tfree=%d\n", i, blocks[i],remainSizeInCurBlock);
    }
    cout<<"#### Recycle List";
    for( int i=0; i< RECYCLE_MAX_INDEX; i++ )
    {
        if( recycleList[i].empty() ) continue;
        cout<<"\n#Index: "<<i<<"\t----"<<endl;
        for(list<MemoryArea*>::iterator iter = recycleList[i].begin();
            iter != recycleList[i].end(); iter++ )
        {
            cout<<(*iter)->getSize()<<"\t";
        }
    }
    cout<<"\n-------------------"<<endl;
}
